
#pragma once
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;
#include "unionfindset.hpp"

#define MAX 2147483647
namespace matrix
{
    template <class V, class W, W MAX_W = MAX, bool Direction = false>
    class Graph
    {
        struct edge
        {
            size_t _srci; //起点下标
            size_t _dsti; //指向下标
            W _w;         //权值
            edge(size_t srci, size_t dsti, W w) : _srci(srci), _dsti(dsti), _w(w)
            {
            }
            bool operator>(const edge &e) const
            {
                return _w > e._w;
            }
        };

        typedef Graph<V, W, MAX_W, Direction> self;

    public:
        Graph() = default;
        Graph(const V *v, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(v[i]);
                _indexmap[v[i]] = i;
            }
            //为存储边的矩阵开辟空间
            _matrix.resize(n);
            for (size_t i = 0; i < _matrix.size(); i++)
            {
                _matrix[i].resize(n, MAX_W);
            }
        }

        //获取下标的接口
        size_t GetVertexIndex(const V &v)
        {
            auto it = _indexmap.find(v);
            if (it != _indexmap.end())
            {
                return _indexmap[v];
            }
            else
            {
                std::cout << "不存在这样的节点" << std::endl;
                return -1;
            }
        }

        void addedge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);
            assert(srci != -1);
            assert(dsti != -1);
            _addedge(srci, dsti, w);
        }

        void Print()
        {
            //先打印顶点
            for (int i = 0; i < _vertexs.size(); i++)
            {
                cout << "[" << i << "]"
                     << "->" << _vertexs[i] << endl;
                ;
            }
            cout << endl;
            // 横下标
            cout << "  ";
            for (size_t i = 0; i < _vertexs.size(); ++i)
            {
                // cout << i << " ";
                printf("%4d", i);
            }
            cout << endl;

            for (size_t i = 0; i < _matrix.size(); ++i)
            {
                cout << i << " "; // 竖下标
                for (size_t j = 0; j < _matrix[i].size(); ++j)
                {
                    // cout << _matrix[i][j] << " ";
                    if (_matrix[i][j] == MAX_W)
                    {
                        // cout << "* ";
                        printf("%4c", '*');
                    }
                    else
                    {
                        // cout << _matrix[i][j] << " ";
                        printf("%4d", _matrix[i][j]);
                    }
                }
                cout << endl;
            }
            cout << endl;
        }
        void _BFS(size_t srci, vector<bool> &visited)
        {
            //遍历队列
            queue<int> q;
            q.push(srci);
            visited[srci] = true;
            int n = _vertexs.size();
            int num = 0;
            int size = 1;
            while (!q.empty())
            {
                cout << "第" << num << "层：" << endl;
                for (int i = 0; i < size; i++)
                {
                    int front = q.front();
                    q.pop();
                    cout << front << ":" << _vertexs[front] << " ";
                    for (int i = 0; i < n; i++)
                    {
                        if (_matrix[front][i] != MAX_W && !visited[i])
                        {
                            q.push(i);
                            visited[i] = true;
                        }
                    }
                    cout << endl;
                }
                num++;
                size = q.size();
            }
            cout << endl;
        }

        void BFS(const V &src)
        {

            //标记数组
            vector<bool> visited(_vertexs.size(), false);
            size_t srci = GetVertexIndex(src);
            _BFS(srci, visited);
            for (int i = 0; i < visited.size(); i++)
            {
                if (!visited[i])
                {
                    cout << endl;
                    _BFS(i, visited);
                }
            }
        }

        /*
                连通图的遍历
                void DFS(const V &src)
                {
                    size_t srci = GetVertexIndex(src);
                    vector<bool> visited(_vertexs.size(), false);
                    _DFS(srci, visited);
                    cout << endl;
                }

        */

        //非连通图的遍历
        void DFS(const V &src)
        {
            size_t srci = GetVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);
            _DFS(srci, visited);
            for (int i = 0; i < visited.size(); i++)
            {
                if (!visited[i])
                {
                    cout << endl;
                    _DFS(i, visited);
                }
            }
            cout << endl;
        }

        //克鲁斯卡尔算法
        W Kruskal(self &minTree)
        {
            size_t n = _vertexs.size();
            minTree._vertexs = _vertexs;
            minTree._indexmap = _indexmap; //深拷贝
            minTree._matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                minTree._matrix[i].resize(n, MAX_W);
            }
            //将所有的边，放入到一个优先级队列中
            priority_queue<edge, vector<edge>, greater<edge>> minque;
            for (size_t i = 0; i < n; i++)
            {
                for (size_t j = 0; j < n; j++)
                {
                    //无向的，保证不重复的选择边
                    if (i < j && _matrix[i][j] != MAX_W)
                    {
                        //将边插入到优先级队列中
                        minque.push(edge(i, j, _matrix[i][j]));
                    }
                }
            }
            //依次选边
            W ret = W();      //总的权值
            int edge_num = 0; //一共要选择n-1条边
            //并查集判断是否有环
            UnionFindSet<V> points;
            //将图的点依次插入到并查集中
            for (int i = 0; i < _vertexs.size(); i++)
            {
                points.insert(_vertexs[i]);
            }
            while (!minque.empty())
            {
                edge min = minque.top();
                minque.pop();
                //判断是否成环
                if (!points.InSet_index(min._srci, min._dsti))
                {
                    //添加边
                    minTree._addedge(min._srci, min._dsti, min._w);
                    points.Union(min._srci, min._dsti);
                    edge_num++;
                    ret += min._w;
                }
            }
            //判断边是否选完
            if (edge_num != n - 1)
         
           {
                return W();
            }

            return ret;
        }

        void PrintShortPath(const V &src, const vector<W> &dist, const vector<int> &pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();
            for (size_t i = 0; i < n; ++i)
            {
                if (i != srci)
                {
                    vector<int> path;
                    size_t parenti = i;
                    while (parenti != srci)
                    {
                        path.push_back(parenti);
                        parenti = pPath[parenti];
                    }
                    path.push_back(srci);
                    reverse(path.begin(), path.end());

                    for (auto index : path)
                    {
                        cout << _vertexs[index] << "->";
                    }
                    cout << "路径长度" << dist[i] << endl;
                }
            }
        }

        W Prim(self &minTree, const V &src)
        {

            size_t n = _vertexs.size();
            int srci = GetVertexIndex(src);
            minTree._vertexs = _vertexs;
            minTree._indexmap = _indexmap;
            minTree._matrix.resize(n);
            for (size_t i = 0; i < n; ++i)
            {
                minTree._matrix[i].resize(n, MAX_W);
            }
            vector<bool> choice(n, false);
            vector<bool> nochoice(n, true);
            priority_queue<edge, vector<edge>, greater<edge>> minque;
            choice[srci] = true;
            nochoice[srci] = false;
            for (size_t i = 0; i < n; i++)
            {
                if (_matrix[srci][i] != MAX_W)
                {
                    minque.push(edge(srci, i, _matrix[srci][i]));
                }
            }
            size_t edge_num = 0;
            W total = W(); //返回值
            while (!minque.empty())
            {
                edge min = minque.top();
                minque.pop();
                //判断当前的边是否合法
                if (choice[min._dsti])
                {
                    // do nothing
                }
                else
                {
                    //将当前边添加到图中
                    minTree._addedge(min._srci, min._dsti, min._w);
                    choice[min._dsti] = true;
                    nochoice[min._dsti] = false;
                    edge_num++;
                    total += min._w;
                    if (edge_num == n - 1)
                    {
                        break;
                    }
                    for (size_t i = 0; i < n; i++)
                    {
                        if (nochoice[i] && _matrix[min._dsti][i] != MAX_W)
                        {
                            minque.push(edge(min._dsti, i, _matrix[min._dsti][i]));
                        }
                    }
                }
            }
            if (edge_num != n - 1)
            {
                return W();
            }
            return total;
        }

        W Prim_(self &minTree, const W &src)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();
            minTree._vertexs = _vertexs;
            minTree._indexmap = _indexmap;
            minTree._matrix.resize(n);
            for (size_t i = 0; i < n; ++i)
            {
                minTree._matrix[i].resize(n, MAX_W);
            }
            vector<bool> X(n, false);
            vector<bool> Y(n, true);
            X[srci] = true;
            Y[srci] = false;

            priority_queue<edge, vector<edge>, greater<edge>> minq;
            for (size_t i = 0; i < n; ++i)
            {
                if (_matrix[srci][i] != MAX_W)
                {
                    minq.push(edge(srci, i, _matrix[srci][i]));
                }
            }
            size_t size = 0;
            W totalW = W();
            while (!minq.empty())
            {
                edge min = minq.top();
                minq.pop();

                if (X[min._dsti])
                {
                }
                else
                {
                    minTree._addedge(min._srci, min._dsti, min._w);
                    X[min._dsti] = true;
                    Y[min._dsti] = false;
                    ++size;
                    totalW += min._w;
                    if (size == n - 1)
                        break;

                    for (size_t i = 0; i < n; ++i)
                    {
                        if (_matrix[min._dsti][i] != MAX_W && Y[i])
                        {
                            minq.push(edge(min._dsti, i, _matrix[min._dsti][i]));
                        }
                    }
                }
            }

            if (size == n - 1)
            {
                return totalW;
            }
            else
            {
                return W();
            }
        }

        //最短路算法 Dijkstra

        // Dijkstra是单源最短路算法，可以计算给定点到其他点的最短路
        void Dijkstra(const V &src, vector<W> &dist, vector<int> &parentindex)
        {
            // dist，记录到i点的当前最短路是多少
            int srci = GetVertexIndex(src);
            size_t n = _vertexs.size();
            dist.resize(n, MAX_W);
            parentindex.resize(n, -1);
            parentindex[srci] = srci;
            vector<bool> visited(n, false);
            //先对dist数组进行初始化
            /*
            for(size_t i=0;i<n;i++){
                if(_matrix[srci][i]!=MAX_W){
                    dist[i]=_matrix[srci][i];
                }
            }
            visited[srci]=true;
            */
            dist[srci] = 0;
            //寻找最短的路径,每一轮对其中一个点进行松弛处理,一共要进行n轮
            for (size_t i = 0; i < n; i++)
            {

                //记录这一轮的最小路径和最小节点
                int min_index = 0;
                W min_num = MAX_W;
                //先找到当前一轮的最小值和最小节点
                for (size_t j = 0; j < n; j++)
                {
                    if (!visited[j] && dist[j] < min_num)
                    {
                        min_num = dist[j];
                        min_index = j;
                    }
                }
                //当前的点为确定点
                visited[min_index] = true;
                //松弛处理
                for (size_t j = 0; j < n; j++)
                {
                    if (!visited[j] && dist[min_index] + _matrix[min_index][j] < dist[j] && _matrix[min_index][j] != MAX_W)
                    {
                        dist[j] = dist[min_index] + _matrix[min_index][j];
                        parentindex[j] = min_index;
                    }
                }
            }
        }

        void Bellman_Ford(const V &src, vector<W> &dist, vector<int> &pPath)
        {
            size_t n = dist.size();
            size_t srci = GetVertexIndex(src);
            dist.resize(n, MAX_W);
            pPath.resize(n, -1);
            dist[srci] = W();
            for (size_t k = 0; k < n - 1; ++k)
            {
                bool exchange = false;
                for (size_t i = 0; i < n; ++i)
                {
                    for (size_t j = 0; j < n; ++j)
                    {
                        // srci->i + i->j < srci->j 则更新路径及权值
                        if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
                        {
                            dist[j] = dist[i] + _matrix[i][j];
                            pPath[j] = i;
                            exchange = true;
                        }
                    }
                }
                if (exchange = false)
                {
                    break;
                }
            }
            for (size_t i = 0; i < n; ++i)
            {
                for (size_t j = 0; j < n; ++j)
                {
                    // 检查有没有负权回路
                    if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
                    {
                        return false;
                    }
                }
            }
        }

        //弗洛伊德算法
        //弗洛伊德算法是一种纯暴力算法
        void FloydWarshall(vector<vector<W>> &vvDist, vector<vector<int>> &vvpPath)
        {
            size_t n = _vertexs.size();
            vvDist.resize(n);
            vvpPath.resize(n);
            for (size_t i = 0; i < n; ++i)
            {
                vvDist[i].resize(n, MAX_W);
                vvpPath[i].resize(n, -1);
            }

            //初始化
            for (size_t i = 0; i < n; i++)
            {
                for (size_t j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != MAX_W)
                    {
                        vvDist[i][j] = _matrix[i][j];
                        vvpPath[i][j] = i;
                    }
                    if (i == j)
                    {
                        vvDist[i][j] = W();
                    }
                }
            }

            //弗洛伊德算法
            //依次以K结点为中转站更新最短路径
            for (size_t k = 0; k < n; k++)
            {
                for (size_t i = 0; i < n; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
                        {
                            vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                            vvpPath[i][j] = vvpPath[k][j];
                        }
                    }
                }
            }

            //打印节点
            for (size_t i = 0; i < n; ++i)
            {
                for (size_t j = 0; j < n; ++j)
                {
                    if (vvDist[i][j] == MAX_W)
                    {
                        // cout << "*" << " ";
                        printf("%3c", '*');
                    }
                    else
                    {
                        // cout << vvDist[i][j] << " ";
                        printf("%3d", vvDist[i][j]);
                    }
                }
                cout << endl;
            }
            cout << endl;
            for (size_t i = 0; i < n; ++i)
            {
                for (size_t j = 0; j < n; ++j)
                {
                    // cout << vvParentPath[i][j] << " ";
                    printf("%3d", vvpPath[i][j]);
                }
                cout << endl;
            }
            cout << "=================================" << endl;
        }

    private:
        void _addedge(size_t srci, size_t dsti, const W &w)
        {
            _matrix[srci][dsti] = w;
            if (Direction == false)
            {
                _matrix[dsti][srci] = w;
            }
        }

        void _DFS(size_t srci, vector<bool> &visited)
        {
            cout << srci << ":" << _vertexs[srci] << " ";
            visited[srci] = true;
            for (int i = 0; i < _vertexs.size(); i++)
            {
                if (_matrix[srci][i] != MAX_W && !visited[i])
                {
                    _DFS(i, visited);
                }
            }
        }

    private:
        unordered_map<V, int> _indexmap; //记录顶点和下标的映射关系
        vector<V> _vertexs;              // 顶点集合的集合
        vector<vector<W>> _matrix;       // 存储边集合的矩阵
    };
}

namespace link_table
{

    template <class V, class W, W MAX_W = INT64_MAX, bool Direction = false>
    class Graph
    {
        typedef Graph<V, W, MAX_W, Direction> self;
        struct edge
        {
            //由于是链表，起点就是当前点，所以一般都省略
            // int _srci;
            size_t _dsti; //目标点
            W _w;         //权值

            //用一个链表将于该顶点相连的顶点连接起来
            edge *_next;
            edge(size_t dsti, const W &w)
                : _dsti(dsti), _w(w), _next(nullptr)
            {
            }
        };

    public:
        Graph() = default;
        Graph(const V *a, size_t n)
        {
            _vertexs.reserve(n);
            //添加顶点
            for (size_t i = 0; i < n; i++)
            {
                _vertexs.push_back(a[i]);
                _indexmap[a[i]] = i;
            }
            _tables.resize(n, nullptr);
        }

        //获取顶点的下标
        size_t GetVertexIndex(const V &v)
        {
            auto it = _indexmap.find(v);
            if (it != _indexmap.end())
            {
                return _indexmap[v];
            }
            else
            {
                std::cout << "不存在这样的节点" << std::endl;
                return -1;
            }
        }

        //添加边
        void addedge(const V &src, const V &dst, const W &w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);
            //头插的方式
            edge *head = _tables[srci];
            edge *eg = new edge(dsti, w);
            eg->_next = head;
            _tables[srci] = eg;
            //如果是无向图
            if (Direction == false)
            {
                edge *eg = new edge(srci, w);
                eg->_next = _tables[dsti];
                _tables[dsti] = eg;
            }
        }

        void Print()
        {
            //打印顶点
            for (size_t i = 0; i < _vertexs.size(); i++)
            {
                cout << "[" << i << "]"
                     << "->" << _vertexs[i] << endl;
            }

            //打印边
            for (size_t i = 0; i < _tables.size(); i++)
            {
                cout << _vertexs[i] << "[ " << i << "]->";
                edge *cur = _tables[i];
                while (cur)
                {
                    cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
                    cur = cur->_next;
                }
                cout << "nullptr" << endl;
            }
        }

    private:
        unordered_map<V, int> _indexmap; //记录顶点和下标的映射关系
        vector<V> _vertexs;              // 顶点集合的集合
        vector<edge *> _tables;          //邻接表
    };
};

